package leetcode_周赛._2021._202111._20211121;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/11/21 14:44
 * 区间内查询数字的频率
 * 请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
 * 子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
 * 请你实现 RangeFreqQuery 类：
 * RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
 * int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
 * 一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。
 * 算法：二分查找
 * 记录每个数所拥有的下标
 * 这样下标就是有序的，使用二分查找找到下标在 [left, right] 之间的最大和最小
 * 然后相减 +1
 */
public class _5186 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 7, 9};
        // 找下标在 4 和 8 之间的
    }

    class RangeFreqQuery {
        List<List<Integer>> all = new ArrayList<>();

        public RangeFreqQuery(int[] arr) {
            for (int i = 0; i <= 10000; i++) {
                all.add(new ArrayList<>());
            }
            for (int i = 0; i < arr.length; i++) {
                // 下标是按顺序加入的，所以是有序的，所以后面可以进行二分
                all.get(arr[i]).add(i);
            }
        }

        public int query(int left, int right, int value) {
            if (all.get(value).size() == 0) return 0;
            List<Integer> now = all.get(value);
            // 第一次二分找左端点下标
            int l = 0, r = now.size() - 1;
            l = binarySearch(now, left, l, r);
            // 不存在这样的左端点
            if (now.get(l) > right || now.get(l) < left) return 0;
            // 第二次二分，找右端点的下标
            r = binarySearch(now, right, l, r);
            if (now.get(r) > right) {
                r--;
            }
            return r - l + 1;
        }

        int binarySearch(List<Integer> nums, int target, int l, int r) {
            while (l < r) {
                int mid = l + r >> 1;
                if (nums.get(mid) < target) l = mid + 1;
                else r = mid;
            }
            return l;
        }

    }

}
